#pragma once

#include<vector>
#include"checkers.h"
#include"myers_functions.h"
#include<random>
vector<int> get_random_string(int length, int alphabet_size)
{
	vector<int> random_string;

	for(int letter = 0; letter < length; ++letter)
	{
		int rand_letter = rand()%alphabet_size + 1; 
		random_string.push_back(rand_letter);
	}

	return random_string;
}

void cool_test()
{
for(int first_length = 1; first_length <= 20; ++first_length, cout << first_length)
	for(int second_length = 1; second_length <= 20; ++second_length)
		for(int alphabet_size = 1; alphabet_size <= 30; ++alphabet_size)
		{
			vector<int>first_string  =  get_random_string(first_length, alphabet_size); 
			vector<int>second_string = get_random_string(second_length, alphabet_size);
			int correct_mistakes = Hirshberg(first_string, second_string);
			int checkin_mistakes = Count_Mistakes(first_string, second_string);
			if (correct_mistakes != checkin_mistakes) throw std::logic_error("check_count_mistakes: FAIL");
			/*{
				for(int i = 0; i<first_length; ++i) cout << first_string[i] << " "; cout << "\n";
				for(int i = 0; i<second_length; ++i) cout << second_string[i] << " "; cout << "\n";
				cout << checkin_mistakes << " " << correct_mistakes << "\n";
				cout << "\n";
				
			}*/
			vector<pair<int, int> >path = Finding_Way(first_string, second_string, correct_mistakes);
			if (check_way(first_string, second_string, correct_mistakes, path)){continue;}

			for(int i = 0; i<first_length; ++i) cerr << first_string[i] << " "; cout << "\n";
			for(int i = 0; i<second_length; ++i) cout << second_string[i] << " "; cout << "\n";
			cout << "wrong_path:\n";
			for(int i = 0; i<path.size(); ++i) cout << path[i].first << " " << path[i].second << "\n";
			cout << "\n";
			return;
		}
	
}

void test_for_make_up_map()
{
	for(int first_length = 1; first_length <= 20; ++first_length)
		for(int second_length = 1; second_length <= 20; ++second_length)
			for(int alphabet_size = 1; alphabet_size <= 30; ++alphabet_size)
			{
				bool flag = true;
				vector<int>first_string  =  get_random_string(first_length, alphabet_size); 
				vector<int>second_string = get_random_string(second_length, alphabet_size);
				
				int mistakes = Hirshberg(first_string, second_string);
				int up_mistakes = (mistakes + 1)/2;
				Mapchik UpMap = Make_Up_Map(first_string, second_string, up_mistakes); 
				vector<vector<int> > shortest_path = Shortest_Path(first_string, second_string); 
			
				for(int diagonal = -up_mistakes; diagonal <= up_mistakes; diagonal += 2)
				{	
					if (diagonal < - second_length)continue;
					if (diagonal > first_length) continue;
					int coord_x = UpMap[diagonal];
					int coord_y = coord_x - diagonal;
					if (coord_x > first_length)continue;
					if (coord_y > second_length)continue;
					if (shortest_path[coord_x][coord_y] > up_mistakes) flag = false;
					if (coord_x + 1 <= first_length && coord_y + 1 <= second_length) 
					{
						if (shortest_path[coord_x + 1][coord_y + 1] == shortest_path[coord_x][coord_y]) flag = false;
					}
				}
				if (!flag) 
				{
					cerr << "Up_Map - problem!\n";
					for(int i = 0; i<first_length; ++i) cerr << first_string[i] << " "; cerr << "\n";
						for(int j = 0; j<second_length; ++j) cerr << second_string[j] << " "; cerr << "\n";

					for(int i = 0; i<=first_length; ++i, cerr << "\n")
						for(int j = 0; j<=second_length; ++j) cerr << shortest_path[i][j] << " ";
					return;
				}
			}
}



void test_for_make_down_map()
{
	for(int first_length = 1; first_length <= 20; ++first_length)
		for(int second_length = 1; second_length <= 20; ++second_length)
			for(int alphabet_size = 1; alphabet_size <= 30; ++alphabet_size)
			{
				int delta = first_length - second_length;
				bool flag = true;
				vector<int>first_string  =  get_random_string(first_length, alphabet_size); 
				vector<int>second_string = get_random_string(second_length, alphabet_size);
				
				int mistakes = Hirshberg(first_string, second_string);
				int down_mistakes = mistakes/2;
				Mapchik DownMap = Make_Down_Map(first_string, second_string, down_mistakes); 

				vector<vector<int> > shortest_path = Shortest_Path_For_Reversed(first_string, second_string); 
			
				for(int diagonal = delta - down_mistakes; diagonal <= delta + down_mistakes; diagonal += 2)
				{	
					if (diagonal < - second_length)continue;
					if (diagonal > first_length) continue;
					int coord_x = DownMap[diagonal];
					int coord_y = coord_x - diagonal;
					if (coord_x < 0)continue;
					if (coord_y < 0)continue;
					if (shortest_path[coord_x][coord_y] > down_mistakes) flag = false;
					if (coord_x - 1 >= 0 && coord_y - 1 >= 0) 
					{
						if (shortest_path[coord_x - 1][coord_y - 1] == shortest_path[coord_x][coord_y]) flag = false;
					}
				}
				if (!flag) 
				{
					cerr << "Down_Map - problem!\n";
					for(int i = 0; i<first_length; ++i) cerr << first_string[i] << " "; cerr << "\n";
						for(int j = 0; j<second_length; ++j) cerr << second_string[j] << " "; cerr << "\n";

					for(int j = 0; j<=second_length; ++j, cerr << "\n")
						for(int i = 0; i<=first_length; ++i)
						 cerr << shortest_path[i][j] << " ";
					return;
				}
			}
}


/*void just_for_fun()
{
	srand(42);
	int first_length = 10000;
	int second_length = 10000;
	int alphabet_size = 2;
	vector<int>first_string  =  get_random_string(first_length, alphabet_size); 
	vector<int>second_string = get_random_string(second_length, alphabet_size);
	ofstream f1("input_myers_1.txt"); for(int i = 0; i<first_length; ++i) f1 << first_string[i] << " ";
	ofstream f2("input_myers_2.txt"); for(int i = 0; i<second_length; ++i) f2 << second_string[i] << " ";
}*/